Termination Proof Script

Consider the TRS R consisting of the rewrite rules
1:    dbl(0)  → 0
2:    dbl(s(X))  → s(n__s(n__dbl(activate(X))))
3:    dbls(nil)  → nil
4:    dbls(cons(X,Y))  → cons(n__dbl(activate(X)),n__dbls(activate(Y)))
5:    sel(0,cons(X,Y))  → activate(X)
6:    sel(s(X),cons(Y,Z))  → sel(activate(X),activate(Z))
7:    indx(nil,X)  → nil
8:    indx(cons(X,Y),Z)  → cons(n__sel(activate(X),activate(Z)),n__indx(activate(Y),activate(Z)))
9:    from(X)  → cons(activate(X),n__from(n__s(activate(X))))
10:    dbl1(0)  → 01
11:    dbl1(s(X))  → s1(s1(dbl1(activate(X))))
12:    sel1(0,cons(X,Y))  → activate(X)
13:    sel1(s(X),cons(Y,Z))  → sel1(activate(X),activate(Z))
14:    quote(0)  → 01
15:    quote(s(X))  → s1(quote(activate(X)))
16:    quote(dbl(X))  → dbl1(X)
17:    quote(sel(X,Y))  → sel1(X,Y)
18:    s(X)  → n__s(X)
19:    dbl(X)  → n__dbl(X)
20:    dbls(X)  → n__dbls(X)
21:    sel(X1,X2)  → n__sel(X1,X2)
22:    indx(X1,X2)  → n__indx(X1,X2)
23:    from(X)  → n__from(X)
24:    activate(n__s(X))  → s(X)
25:    activate(n__dbl(X))  → dbl(activate(X))
26:    activate(n__dbls(X))  → dbls(activate(X))
27:    activate(n__sel(X1,X2))  → sel(activate(X1),activate(X2))
28:    activate(n__indx(X1,X2))  → indx(activate(X1),X2)
29:    activate(n__from(X))  → from(X)
30:    activate(X)  → X
There are 33 dependency pairs:
31:    DBL(s(X))  → S(n__s(n__dbl(activate(X))))
32:    DBL(s(X))  → ACTIVATE(X)
33:    DBLS(cons(X,Y))  → ACTIVATE(X)
34:    DBLS(cons(X,Y))  → ACTIVATE(Y)
35:    SEL(0,cons(X,Y))  → ACTIVATE(X)
36:    SEL(s(X),cons(Y,Z))  → SEL(activate(X),activate(Z))
37:    SEL(s(X),cons(Y,Z))  → ACTIVATE(X)
38:    SEL(s(X),cons(Y,Z))  → ACTIVATE(Z)
39:    INDX(cons(X,Y),Z)  → ACTIVATE(X)
40:    INDX(cons(X,Y),Z)  → ACTIVATE(Y)
41:    INDX(cons(X,Y),Z)  → ACTIVATE(Z)
42:    FROM(X)  → ACTIVATE(X)
43:    DBL1(s(X))  → DBL1(activate(X))
44:    DBL1(s(X))  → ACTIVATE(X)
45:    SEL1(0,cons(X,Y))  → ACTIVATE(X)
46:    SEL1(s(X),cons(Y,Z))  → SEL1(activate(X),activate(Z))
47:    SEL1(s(X),cons(Y,Z))  → ACTIVATE(X)
48:    SEL1(s(X),cons(Y,Z))  → ACTIVATE(Z)
49:    QUOTE(s(X))  → QUOTE(activate(X))
50:    QUOTE(s(X))  → ACTIVATE(X)
51:    QUOTE(dbl(X))  → DBL1(X)
52:    QUOTE(sel(X,Y))  → SEL1(X,Y)
53:    ACTIVATE(n__s(X))  → S(X)
54:    ACTIVATE(n__dbl(X))  → DBL(activate(X))
55:    ACTIVATE(n__dbl(X))  → ACTIVATE(X)
56:    ACTIVATE(n__dbls(X))  → DBLS(activate(X))
57:    ACTIVATE(n__dbls(X))  → ACTIVATE(X)
58:    ACTIVATE(n__sel(X1,X2))  → SEL(activate(X1),activate(X2))
59:    ACTIVATE(n__sel(X1,X2))  → ACTIVATE(X1)
60:    ACTIVATE(n__sel(X1,X2))  → ACTIVATE(X2)
61:    ACTIVATE(n__indx(X1,X2))  → INDX(activate(X1),X2)
62:    ACTIVATE(n__indx(X1,X2))  → ACTIVATE(X1)
63:    ACTIVATE(n__from(X))  → FROM(X)
The approximated dependency graph contains 4 SCCs: {32-42,54-63}, {46}, {43} and {49}.
Tyrolean Termination Tool  (4.45 seconds)   ---  May 3, 2006